import java.util.ArrayDeque;
import java.util.Deque;

public class Sort {
    public static void swap(int[] array, int start, int end) {
        int tmp = array[start];
        array[start] = array[end];
        array[end] = tmp;
    }

    /**
     *1. end为闭区间
     *2. 找基准值下标(挖坑法)
     */
    public static int partition(int[] array, int start, int end) {
        int left = start;
        int right = end;
        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    //快速排序（挖坑法）
    public static void quickSort(int[] array, int start, int end) {
        int left = start;
        int right = end;
        if (left >= right) {
            return;
        }
        int index = partition(array, left, right);
        quickSort(array, left, index - 1);
        quickSort(array, index + 1, right);
    }

    //三数取中法(防止序列本身就是有序的而导致栈溢出)
    public static void quickSort1(int[] array, int start, int end) {
        int left = start;
        int right = end;
        if (left >= right) {
            return;
        }
        int minindex = partition(array, left, right);
        swap(array, start, end);

        int index = partition(array, left, right);
        quickSort(array, left, index - 1);
        quickSort(array, index + 1, right);
    }

    //找到中间大那个值的下标
    public static int minIndex(int[] array, int start, int end) {
        int mid = (start + end) / 2;
        if (array[start] > array[end]) {
            if (array[start] < array[mid]) {
                return start;
            } else if (array[end] > array[mid]) {
                return end;
            } else {
                return mid;
            }
        } else {
            if (array[start] > array[mid]) {
                return start;
            } else if (array[end] < array[mid]) {
                return end;
            } else {
                return mid;
            }
        }
    }

    //非递归法快速排序(运用栈)
    public static void quickSort2(int[] array) {
        int start = 0;
        int end = array.length - 1;//开区间
        Deque<Integer> Stack = new ArrayDeque();
        Stack.push(start);
        Stack.push(end);
        while (!Stack.isEmpty()) {
            int right = Stack.pop();
            int left = Stack.pop();

            if (right - left <= 1) {
                continue;
            }
            //如果下标成立再找基准值下标
            int index = partition(array, left, right);

            Stack.push(index + 1);
            Stack.push(right);

            Stack.push(left);
            Stack.push(index - 1);
        }
    }
    //加上直接插入排序的快速排序
    public static void quickSort3(int[] array, int start, int end) {
        int left = start;
        int right = end;
        if (left >= right) {
            return;
        }
        if ((right - end) == 2) {
            insertSort(array, left, right);
            return;
        }
        int index = partition(array, left, right);
        quickSort(array, left, index - 1);
        quickSort(array, index + 1, right);
    }
    //直接插人排序
    public static void insertSort(int[] array, int left, int right) {
        for (int i = left; i <= right; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= left; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    array[j + 1] = tmp;
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }


}
